package nbranch.tree.postOrder;

import java.util.LinkedList;
import java.util.List;

import nbranch.tree.perorder.Node;

/**
 * @Date 2020/03/16
 * @author 王光浩
 * @Thinking 使用迭代。
 * @Analysis 时间复杂度O（n），空间复杂度O（3n）
 */
public class MyMethodTwo {
	public List<Integer> postorder(Node root) {
        List<Integer> res=new LinkedList<Integer>();
		if(root==null)return res;
        LinkedList<List<Node>> stack=new LinkedList<>();
        if(root.children!=null && !root.children.isEmpty())
        	stack.add(root.children);
        List<Node> children;
        //后序遍历
        while(!stack.isEmpty()) { 
        	//获取第一节点的所有子节点
        	children=stack.peek().get(0).children; 
        	while(children!=null && !children.isEmpty()) {
        		stack.push(children);
        		children=stack.peek().get(0).children;
        	}
        	children=stack.peek();
        	res.add(children.remove(0).val);
        	if(stack.peek().isEmpty())stack.poll();
        }
        res.add(root.val);
        return res;
    }
}
